package MyLinkedList;
public class MyLinkedList {
    // 节点类
    private static class Node {
        int val;
        Node prev;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    private Node head; // 头节点
    private Node last; // 尾节点
    private int size; // 链表长度

    public MyLinkedList() {
        head = null;
        last = null;
        size = 0;
    }

    // 头插法
    public void addFirst(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            last = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    // 尾插法
    public void addLast(int val) {
        Node newNode = new Node(val);
        if (last == null) {
            head = newNode;
            last = newNode;
        } else {
            newNode.prev = last;
            last.next = newNode;
            last = newNode;
        }
        size++;
    }

    // 任意位置插入，第一个数据节点为0号下标
    public void addIndex(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Invalid index: " + index);
        }
        if (index == 0) {
            addFirst(val);
        } else if (index == size) {
            addLast(val);
        } else {
            Node newNode = new Node(val);
            Node current = getNode(index);
            Node prevNode = current.prev;

            newNode.prev = prevNode;
            newNode.next = current;
            prevNode.next = newNode;
            current.prev = newNode;
            size++;
        }
    }

    // 查找是否包含关键字 key 是否在双向链表中
    public boolean contains(int key) {
        Node current = head;
        while (current != null) {
            if (current.val == key) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 删除第一次出现关键字为 key 的节点
    public void remove(int key) {
        Node current = head;
        while (current != null) {
            if (current.val == key) {
                Node prevNode = current.prev;
                Node nextNode = current.next;

                if (prevNode == null) {
                    head = nextNode;
                } else {
                    prevNode.next = nextNode;
                }
                if (nextNode == null) {
                    last = prevNode;
                } else {
                    nextNode.prev = prevNode;
                }
                size--;
                return;
            }
            current = current.next;
        }
    }

    // 删除所有值为 key 的节点
    public void removeAllKey(int key) {
        Node current = head;
        while (current != null) {
            if (current.val == key) {
                Node prevNode = current.prev;
                Node nextNode = current.next;

                if (prevNode == null) {
                    head = nextNode;
                } else {
                    prevNode.next = nextNode;
                }
                if (nextNode == null) {
                    last = prevNode;
                } else {
                    nextNode.prev = prevNode;
                }
                size--;
            }
            current = current.next;
        }
    }

    // 得到双向链表的长度
    public int size() {
        return size;
    }

    // 显示链表中的元素
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    // 清空链表
    public void clear() {
        head = null;
        last = null;
        size = 0;
    }

    // 辅助方法：根据索引获取节点
    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Invalid index: " + index);
        }
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }
}

